import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:
 * Date: 2024-09-22
 * Time: 9:49
 */
public class TestHeap {
    public int[] elem;
    public int useSize;

    public TestHeap(){
        this.elem = new int[10];
    }

    public void intelem(int[] array){
        for (int i = 0; i < array.length; i++) {
            this.elem[i] = array[i];
            useSize++;
        }
    }

    public void createHeap(){
        for (int parent = (this.useSize-1-1)/2; parent >= 0; parent--) {
            shifDown(parent, this.useSize);
        }
    }

    public void shifDown(int parent, int useSize){
        int child = 2*parent + 1;
        while(child < useSize){
            //左右子树的最大值
            if(child+1 < useSize && elem[child+1] > elem[child]){
                child++;
            }
            if(elem[child] > elem[parent]){
                swap(elem, child, parent);
                parent = child;
                child = 2*parent+1;
            }else{
                break;
            }
        }
    }

    public void swap(int[] elem, int child, int parent){
        int tmp = elem[child];
        elem[child] = elem[parent];
        elem[parent] = tmp;
    }

    public void offer(int val){
        if(isFull()){
            grow();
        }
        elem[useSize] = val;
        sitUp(useSize);
        useSize++;
    }

    public void sitUp(int child){
        int parent = (child -1)/2;
        while(parent > 0){
            if(elem[parent] < elem[child]){
                swap(elem,child,parent);
                child = parent;
                parent = (child-1)/2;
            }else{
                break;
            }
        }
    }

    public boolean isFull(){
        return elem.length == useSize;
    }

    public void grow(){
        elem = Arrays.copyOf(elem, 2*elem.length);
    }
}
